1. Field of the Invention
The present invention relates to techniques for digital-image processing, including motion estimation techniques, and has been developed with particular attention paid to its possible application to the processing of television images and to the display of the television signal on displays, such as personal-computer displays of the cathode-ray type, liquid-crystal type or plasma type, which use a progressive-scanning mechanism.
Even though in what follows, for reasons of clarity and simplicity of exposition, practically exclusive reference will be made to this application, it must in any case be borne in mind that the significance of application of the invention is more general. The invention is in fact applicable to all techniques of digital-image processing in which there arise operating conditions of the type described in what follows.
2. Description of the Related Art
The television system adopted in Europe, i.e., the Phase-Alternate-Line (PAL) system, is characterized by a frame frequency of 25 Hz: this means that it is possible to display 25 images or frames per second, each of which is made up of a grid of 720×576 samples, called pixels (picture elements), arranged in rows. In fact, the raster, i.e., the electron beam that draws the image on the television display, operates at a frequency of 50 Hz, and once every second creates on the display 50 half-images, or fields, each of which is sampled at a different instant in time, with a time interval between said fields of one fiftieth of a second. Each field contains alternately the even rows only or else the odd rows only of a complete image. Consequently, the images displayed on the television screen have their even rows belonging to one field, referred to as even field, and their odd rows belonging to another field, referred to as odd field. When the images are divided in this way, they are referred to as “interlaced” images.
The PAL system was originally conceived for systems with cathode-ray displays, but television images are not suited for being displayed on other types of display, such as, for example, computer monitors, or modern televisions with plasma or liquid-crystal displays. These systems, in fact, use a display mechanism referred to as “progressive”, which each time composes on the display a complete image, and not a single field. A television video sequence in PAL format, displayed on these systems, would cause an unpleasant “mosaic” effect, due to the fact that each image is in effect made up of two different interlaced fields.
To display the images correctly, it is therefore necessary to subject them to a de-interlacing procedure, which provides for reconstruction of a complete image, starting from a single field. In the case of even fields, the odd lines of the image are reconstructed; in the case of odd fields, the even lines of the image are reconstructed. The reconstructed lines are then added to the original ones, and a complete image or frame is thus obtained.
The de-interlacing procedure can be carried out in different ways, which can be reduced to two main categories:
motion-compensated procedures; and
non-motion-compensated procedures.
Motion-compensated (or temporal) de-interlacing procedures use motion-estimation techniques for reconstructing a field starting from temporally preceding and subsequent information, whilst non-motion-compensated (or spatial) de-interlacing procedures use spatial interpolation for reconstructing the even or odd rows of a frame, starting from the odd or even rows, respectively.
To carry out the procedure of non-motion-compensated de-interlacing of digital images, it is known to use a procedure referred to as Edge-Line Averaging (ELA).
FIG. 1 illustrates a part of the pixels of an image or frame FRM. In this frame FRM, the odd rows that make up a field to be reconstructed MFD are to be reconstructed starting from the even rows. According to the ELA procedure, the pixels belonging to row N, where N is an odd integer, can be reconstructed starting from the adjacent pixels, belonging to the rows N−1 and N+1.
In particular, if a pixel to be reconstructed X of the field MFD is in the position M on the row N of the frame FRM, it can be reconstructed using the pixels in the positions M−1, M and M+1 on the aforesaid rows.
If A, B and C designate the pixels belonging to a work window FL in positions M−1, M and M+1 in the row N−1 of the frame FRM, and D, E and F designate the pixels in positions M−1, M and M+1 in the row N+1 of the frame FRM, the pixel to be reconstructed X can be reconstructed using the following interpolation formula:
                    X        =                  {                                                                                                                                                                  A                          +                          F                                                2                                            ⁢                      if                      ⁢                                                                                                A                          -                          F                                                                                                              <                                                                                        B                        -                        E                                                                                                    ,                                                                                C                      -                      D                                                                                                                                                                                                                                                            B                          +                          E                                                2                                            ⁢                      if                      ⁢                                                                                                B                          -                          E                                                                                                              <                                                                                        A                        -                        F                                                                                                    ,                                                                                C                      -                      D                                                                                                                                                                                                                                                            C                          +                          D                                                2                                            ⁢                      if                      ⁢                                                                                                C                          -                          D                                                                                                              <                                                                                        A                        -                        F                                                                                                    ,                                                                                B                      -                      E                                                                                                                                                  (        1        )            
In other words, as can also be inferred from FIG. 1, the pixel X to be reconstructed is reconstructed by linear interpolation of the most correlated pair of pixels belonging to the nearest rows of the field of opposite parity, the correlation between two pixels being defined as the distance of the respective values.
To carry out, instead, the procedure of motion-compensated, or temporal, de-interlacing of digital images for composing the field to be reconstructed MFD, illustrated in FIG. 2, this field to be reconstructed MFD is, instead, broken down into a series of blocks BK. Each block BK is reconstructed by interpolation of two blocks BKm, BKn belonging to another two frames, of the same parity, that temporally precede and follow, respectively, the frame to be reconstructed containing the field to be reconstructed MFD. The preceding frame includes a field n that contains the block BKn and the following frame includes a field m that contains the block BKm.
The pair of blocks is chosen by minimizing a correlation function, such as, for example, the Sum-of-Absolute-Differences (SAD) function, which is defined as follows: if SAD(x,y) is the SAD function between a preceding block BKn of W×H pixels (where W and H are positive integers), set in a position (x,y) in the preceding field n, which has pixels of intensity Vn(x+i,y+j), and a corresponding subsequent block BKm, set in a position (x+dx,y+dy) in the subsequent field m, which has pixels of intensity Vm(x+dx+i,y+dy+j), then the SAD function is:
                              SAD          ⁡                      (            xy            )                          =                                            ∑                              i                =                0                            W                        ⁢                                                  ⁢                                          ∑                                  j                  =                  0                                H                            ⁢                                                          ⁢                                                V                  n                                ⁡                                  (                                                            x                      +                      i                                        ,                                          y                      +                      j                                                        )                                                              -                                    V              m                        ⁡                          (                                                x                  +                  dx                  +                  i                                ,                                  y                  +                  dy                  +                  j                                            )                                                          (        2        )            
The position of the preceding reference block BKn with respect to the block BK to be reconstructed is indicated by a motion vector MV, whilst the position of the subsequent block BKm is indicated by an equal and opposite motion vector designated by −MV in FIG. 2. In this case, the term “balanced motion estimation” is used, in so far as the two reference blocks, the preceding one BKn and the subsequent one BKm, are in an opposite position with respect to that of the block BK to be reconstructed.
For minimizing the correlation function, whether it is the aforesaid SAD function or any other function, it is possible to use any technique of motion estimation, such as for example the full-search technique, which verifies exhaustively all the possibilities within a certain search area, called “search window”.
The de-interlacing procedures listed above, however, do not succeed in guaranteeing optimal performance in all the situations that can occur during processing of a video sequence.